From albanycs!leah:rsb584 Wed Apr  6 17:30:46 1988
Received: by albanycs.albany.edu (5.54/4.8)
	id AA28065; Wed, 6 Apr 88 11:55:31 EST
Date: Wed, 6 Apr 88 12:55:22 EDT
From: albanycs!leah:rsb584 (Raymond S Brand)
Received: by leah.Albany.EDU (5.58/1.1)
	id AA02145; Wed, 6 Apr 88 12:55:22 EDT
Message-Id: <8804061655.AA02145@leah.Albany.EDU>
To: albanycs:beowulf!rsbx
Subject: circlept3.txt

>From guy@SHERLOCK.PC.CS.CMU.EDU Mon Apr  4 23:05:59 1988
Path: leah!itsgw!nysernic!cmx!batcomputer!cornell!rochester!PT.CS.CMU.EDU!SHERLOCK.PC.CS.CMU.EDU!guy
From: guy@SHERLOCK.PC.CS.CMU.EDU (Guy Jacobson)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Summary: The answer.
Message-ID: <1314@PT.CS.CMU.EDU>
Date: 5 Apr 88 03:05:59 GMT
References: <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu>
Sender: netnews@PT.CS.CMU.EDU
Organization: Carnegie-Mellon University, CS/RI
Lines: 34

This is an old and very basic problem in computational geometry (and
operations research) first posed by Sylvester in 1857 [J. J. Sylvester, `` A
Question in the Geometry of Situation'', _Quart._J._Math._ 1 (1857)].  The
problem has received much attention over the years.  In 1982, Megiddo showed
how to solve the problem in linear time, improving on the previous n log n
bound of Hoey and Shamos [N. Megiddo, ``Linear-time Algorithms for Linear
Programming in R^3 and Related Problems'', in Proc. 23rd. FOCS (1982), pp.
329-338].

TRUE FACT:  The smallest circle enclosing all the points is a circle with
two of the points as a diameter (if some such circle encloses all the other
points), or the circumscribing circle of three (or more, in degenerate
cases) of the points.  Think of a circularly constrained hoop shrinking in
from infinity to convince yourself of this.

The naive algorithm generates all pairs of points (as potential diameters)
and checks if all the other points are inside the circle with those pairs as
diameters.  If such pairs exist, the one with smallest diameter defines the
smallest enclosing circle.  If no pair forms the diameter of an enclosing
circle, then all triples are checked; again the triple whose circumscribing
circle encloses all the points with smallest diameter defines the desired
circle (this HAS To succeed, from the TRUE FACT above).  This algorithm
takes n^4 time as presented.

Hoey and Shamos's algorithm uses the farthest-point Voronoi diagram, and was
the first algorithm proved to run in o(n^3) time.

Megiddo's algorithm is too complex to be included here.  It proceeds to make
a series of passes through the points, discarding those that cannot possibly
be on the boundary of the desired circle.  In each pass, it is guaranteed to
discard at least a fixed fraction (1/16) of the points from consideration;
this proves the linear time bound.

-- Guy